/*
 * @lc app=leetcode.cn id=698 lang=typescript
 *
 * [698] 划分为k个相等的子集
 */

// @lc code=start

function dfs(
  s: number,
  sum: number,
  per: number,
  nums: number[],
  n: number,
  visited: boolean[]
): boolean {
  if (s === 0) return true;
  if (!visited[s]) return visited[s];
  visited[s] = false;
  for (let i = 0; i < n; i++) {
    if (nums[i] + sum > per) break;
    // 当前数字可用
    if (((s >> i) & 1) !== 0) {
      if (dfs(s ^ (1 << i), (nums[i] + sum) % per, per, nums, n, visited)) {
        return true;
      }
    }
  }

  return false;
}

function canPartitionKSubsets(nums: number[], k: number): boolean {
  const total = nums.reduce((acc, cur) => acc + cur);
  // 总和不能整除
  if (total % k !== 0) return false;
  // 平均数
  const n = nums.length;
  const per = total / k;
  nums.sort((a, b) => a - b);
  // 有数字大于平均数，表示不能分割
  if (nums[n - 1] > per) return false;

  // 表示当前状态是否可用
  const visited: boolean[] = new Array(1 << n).fill(true);

  return dfs((1 << n) - 1, 0, per, nums, n, visited);
}
// @lc code=end
